package greed;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/lhmp26/
//现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为 正整数。请返回每段竹子长度的 最大乘积 是多少。
//答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
public class LCR_132砍竹子2 {
    static public int cuttingBamboo(int bamboo_len) {
        if(bamboo_len <= 3) return bamboo_len - 1;
        int b = bamboo_len % 3, p = 1000000007;
        long rem = 1, x = 3;
        for(int a = bamboo_len / 3 - 1; a > 0; a /= 2) {
            if(a % 2 == 1) rem = (rem * x) % p;
            x = (x * x) % p;
        }
        if(b == 0) return (int)(rem * 3 % p);
        if(b == 1) return (int)(rem * 4 % p);
        return (int)(rem * 6 % p);
    }

    public static void main(String[] args) {
    }
}
